Euler Problem 179

Find the number of integers $1 < n < 10^7$, for which $n$ and $n + 1$ have the same number of positive divisors. For example, 14 has the positive divisors 1, 2, 7, 14 while 15 has 1, 3, 5, 15.



In [2]:

    
N = 10 ** 7
div = [1]*(N+1)
for p in range(2,N+1):
    if div[p] == 1:
        div[p] = p
        for k in range(p*p, N+1, p):
            div[k] = p
count = 0
for n in range(2, N+1):
    p = div[n]
    m = n//p
    div[n] = div[m]
    while m % p == 0:
        m //= p
    div[n] += div[m]
    count += (div[n] == div[n-1])
print(count)



In [ ]: